package a2022.a20220601;

import java.util.Arrays;

/**
 * @author lenovo
 * @date 2022/6/1
 */
public class a {
    public static void main(String[] args) {

        int[] matchsticks = {5,5,5,5,4,4,4,4,3,3,3,3};
        boolean makesquare = makesquare(matchsticks);
        System.out.println(makesquare);
    }
    public static boolean makesquare(int[] matchsticks) {
        int totalLen = Arrays.stream(matchsticks).sum();
        if (totalLen % 4 != 0) {
            return false;
        }
        Arrays.sort(matchsticks);
        for (int i = 0, j = matchsticks.length - 1; i < j; i++, j--) {
            int temp = matchsticks[i];
            matchsticks[i] = matchsticks[j];
            matchsticks[j] = temp;
        }

        int[] edges = new int[4];
        return dfs(0, matchsticks, edges, totalLen / 4);
    }

    /**
     *
     * @param index 指针
     * @param matchsticks 从大到小排序后的数组
     * @param edges 边长数组
     * @param len 边长
     * @return
     */
    public static boolean dfs(int index, int[] matchsticks, int[] edges, int len) {
        if (index == matchsticks.length) {
            return true;
        }
        for (int i = 0; i < edges.length; i++) {
            edges[i] += matchsticks[index];
            if (edges[i] <= len && dfs(index + 1, matchsticks, edges, len)) {
                return true;
            }
            edges[i] -= matchsticks[index];
        }
        return false;
    }
//    public static boolean makesquare(int[] matchsticks) {
//        int length = matchsticks.length;
//        //排序
//        Arrays.sort(matchsticks);
//        //计算总和
//        long all = Arrays.stream(matchsticks).sum();
//        //判断是否可以形成正方形
//        if (all % 4 != 0) return false;
//        long side = all / 4;
//        long x = 0;
//        for (int i = 0; i < length; i++) {
//            x += matchsticks[i];
//            if (x == side) x = 0;
//            if (x > side) return false;
//        }
//        return true;
//    }
}
